
/********************************************
 * Given a heap of integers, in which there
 * is only a integer whose number is odd,
 * while other integers' numbers are even.
 * Which integer's number is odd?
 *
 * Date: 6/1/2008
 *******************************************/
 
#include <stdio.h>

void swap( int *a, int *b)
{
    int t;
    t = *b;
    *b = *a;
    *a = t;
}

int abs( int a )
{
    return a<0 ? -a : a;
}

void balance( int *a, int *b, int *c )
{
    if ( abs(*a-*b) < abs(*a-*c) ) swap(b,c);
    if ( abs(*b-*c) < abs(*a-*c) ) swap(b,a);
}

void print( int a[], int len )
{
    int i;

    for ( i = 0; i < len; i++ )
		printf("%d ", a[i]);
	printf("\n");
    return;
}

#define len(a) (sizeof(a) / sizeof(a[0]))

int main()
{
    int i, j, m;
    int left, right;
    int a[] = { 13, 20, 13, 21, 17, 21, 20, 17, 31, 31, 13 };

    print( a, len(a) );
    do{
	left = right = 0;
	m =  len(a) / 2;
	i= m - 1; j = m + 1;
	while ( i >= 0 ){
	    balance( &a[i], &a[m], &a[j] );
	    if ( left == right );
	    else if ( left > right && a[i] > a[j] ) swap( &a[i], &a[j] );
	    else if ( right > left && a[j] > a[i] ) swap( &a[i], &a[j] );
	    left += a[i];
	    right += a[j];
	    i--, j++;
	}
	print( a, len(a) );

    }while( left != right );

	printf("%d\n", a[m]);

    return 0;
}
